Feature #4: Query Peak Users

Implementing the "Query Peak Users" feature for our "Cellular Operator AT&T" project.

Description#

The cellular operator serves a rectangular region, represented by a 2D grid with one base station in each cell. Each base station is limited in the number of simultaneous users. During busy hours, some users get poor or no service. The company leadership wants to fix this problem by deploying multiple base stations, wherever necessary. Since this is a capital-intensive plan, we want to systematically deploy new base stations only where they are bound to help the most.

The operator has gathered the peak number of users connected to each base station. The executives want to query the obtained data and calculate the peak number of users that are connected to the base stations in a rectangular subset of the covered area. The executives may need to query the data multiple times. Therefore, we need to figure out an efficient way to execute the queries and return their results.

Note: The area to be queried is identified by the top-left and bottom-right cell coordinates.

The following illustration will help clarify to this problem:

Created with Fabric.js 3.6.6 1 3 4 8 2 4 7 6 4 5 7 9 3 2 3 8 5 8 1 8 2 0 9 5 2 4 1 7 0 7 Given the top-left (1, 2) and bottom-right (3, 5) coordinates of the rectangularregion, we calculate the sum of all the users in the rectangular region and return 50 as the sum.
Peak users in a rectangular region

1 of 2

Created with Fabric.js 3.6.6 1 3 4 8 2 4 7 6 4 5 7 9 3 2 3 8 5 8 1 8 2 0 9 5 2 4 1 7 0 7 Given the top-left (1, 0) and bottom-right (2, 3) coordinates of the rectangularregion, we calculate the sum of all the users in the rectangular region and return 45 as the sum.
Peak users in a rectangular region

2 of 2

Solution#

A beginner’s way of solving this problem is to use nested loops to iterate over the rectangular region, represented by the top-left (row1,col1)(row1, col1) and bottom-right (row2,col2)(row2, col2) coordinates, and sum up all the elements in that region.

Since the executives may want to query the data multiple times, it would make sense for us to perform some pre-processing.

Caching#

We could use extra space for speeding up the algorithm by pre-calculating all the possible rectangular regions and storing them in a hash map. This way, all the queries will take constant time. However, the space complexity will blow up, because we have to store all the possible regions.

Let’s see how we can build on this intuition of caching the results.

Caching rows#

Imagine pre-computing the cumulative sum of the elements for each row in the grid. We can derive a formula that will calculate the cumulative sum for each individual row ii, ranging from 0...rows10 ...rows - 1 (inclusive):

cache[i][j]={k=0j1users[i][k]j>00j=0cache[i][j]=\begin{cases}\sum_{k=0}^{j-1} users[i][k]& j \gt 0 \\ 0 & j = 0\end{cases}

Here, jj ranges from 00 to the total number of columns, (cols)(cols) in the input grid users. We will calculate the prefix sum of all the cells in a row and store them at the appropriate cell in a 2D grid cache of order rows×cols+1rows \times cols + 1. We can simplify the notation given above and make use of the sum calculated in the last iteration:

cache[i][j+1]={users[i][j]+cache[i][j]j>00j=0cache[i][j + 1]=\begin{cases} users[i][j]+cache[i][j] & j \gt 0 \\ 0 & j = 0\end{cases}

Note: We can observe from our formulation that the cache grid will have an additional column, which will contain only zeros.

Let’s review the following illustration to understand this formulation better:

Created with Fabric.js 3.6.6 1 4 7 2 5 8 3 6 9 0 0 0 0 0 0 0 0 0 0 0 0 Input Grid Cache Grid We initialize the cache grid with zeros in each of its cells.
Pre-computing the cumulative sum

1 of 11

Created with Fabric.js 3.6.6 Input Grid Cache Grid 1 4 7 2 5 8 3 6 9 0 0 0 1 0 0 0 0 0 0 0 0 We iterate over the cells of both the grids one by one,updating the value of the next column in the cache grid.
Pre-computing the cumulative sum

2 of 11

Created with Fabric.js 3.6.6 Input Grid Cache Grid We iterate over the cells of both the grids one by one,updating the value of the next column in the cache grid. 0 0 0 1 0 0 3 0 0 0 0 0 1 4 7 2 5 8 3 6 9
Pre-computing the cumulative sum

3 of 11

Created with Fabric.js 3.6.6 Input Grid Cache Grid We iterate over the cells of both the grids one by one,updating the value of the next column in the cache grid. 0 0 0 1 0 0 3 0 0 6 0 0 1 4 7 2 5 8 3 6 9
Pre-computing the cumulative sum

4 of 11

Created with Fabric.js 3.6.6 Input Grid Cache Grid We iterate over the cells of both the grids one by one,updating the value of the next column in the cache grid. 0 0 0 1 4 0 3 0 0 6 0 0 1 4 7 2 5 8 3 6 9
Pre-computing the cumulative sum

5 of 11

Created with Fabric.js 3.6.6 Input Grid Cache Grid We iterate over the cells of both the grids one by one,updating the value of the next column in the cache grid. 1 4 7 2 5 8 3 6 9 0 0 0 1 4 0 3 9 0 6 0 0
Pre-computing the cumulative sum

6 of 11

Created with Fabric.js 3.6.6 Input Grid Cache Grid We iterate over the cells of both the grids one by one,updating the value of the next column in the cache grid. 1 4 7 2 5 8 3 6 9 0 0 0 1 4 0 3 9 0 6 15 0
Pre-computing the cumulative sum

7 of 11

Created with Fabric.js 3.6.6 Input Grid Cache Grid We iterate over the cells of both the grids one by one,updating the value of the next column in the cache grid. 1 4 7 2 5 8 3 6 9 0 0 0 1 4 7 3 9 0 6 15 0
Pre-computing the cumulative sum

8 of 11

Created with Fabric.js 3.6.6 Input Grid Cache Grid We iterate over the cells of both the grids one by one,updating the value of the next column in the cache grid. 0 0 0 1 4 7 3 9 15 6 15 0 1 4 7 2 5 8 3 6 9
Pre-computing the cumulative sum

9 of 11

Created with Fabric.js 3.6.6 Input Grid Cache Grid We iterate over the cells of both the grids one by one,updating the value of the next column in the cache grid. 0 0 0 1 4 7 3 9 15 6 15 24 1 4 7 2 5 8 3 6 9
Pre-computing the cumulative sum

10 of 11

Created with Fabric.js 3.6.6 Input Grid Cache Grid 0 0 0 1 4 7 3 9 15 6 15 24 1 4 7 2 5 8 3 6 9 Each cell in the cache grid contains the prefix sum for that row.
Pre-computing the cumulative sum

11 of 11

Once we have cached the prefix sums, we can accumulate the sum in the region row by row. The subset region is identified by the starting and ending cell coordinates, (row1,col1)(row1, col1) and (row2,col2)(row2, col2). We can derive a formula for calculating the sum as well:

sum[row1...row2][col1...col2]=i=row1row2cache[i][col2+1]cache[i][col1]sum[row1...row2][col1...col2] = \sum_{i=row1}^{row2} cache[i][col2 + 1] - cache[i][col1]

As the cache[i][col2+1]cache[i][col2 + 1] contains the prefix sum of the elements up to that column, that is, col2+1col2 + 1 (exclusive), we will need to subtract the cells that are not part of the subset region, which is, cache[i][col1]cache[i][col1].

Let’s review an example of this:

Created with Fabric.js 3.6.6 Input Grid Cache Grid 0 0 0 1 4 7 3 9 15 6 15 24 1 4 7 2 5 8 3 6 9 Given the starting and ending coordinates of the subset region (0, 1) and (2, 2), we will use the pre-computed cache grid to calculate the sum row by row. Initially, sum = zero.
Calculate the peak number of users

1 of 5

Created with Fabric.js 3.6.6 Input Grid Cache Grid 1 4 7 2 5 8 3 6 9 0 0 0 1 4 7 3 9 15 6 15 24 We iterate over the rows, starting from row1, 0 in this case,till the row2, 2. Here, sum = sum + cache[0][3] - cache[0][1].sum = 0 + 6 - 1 = 5
Calculate the peak number of users

2 of 5

Created with Fabric.js 3.6.6 Input Grid Cache Grid 1 4 7 2 5 8 3 6 9 0 0 0 1 4 7 3 9 15 6 15 24 We iterate over the rows, starting from row1, 0 in this case,till the row2, 2. Here, sum = sum + cache[1][3] - cache[1][1].sum = 5 + 15 - 4 = 16
Calculate the peak number of users

3 of 5

Created with Fabric.js 3.6.6 Input Grid Cache Grid 1 4 7 2 5 8 3 6 9 0 0 0 1 4 7 3 9 15 6 15 24 We iterate over the rows, starting from row1, 0 in this case,till the row2, 2. Here, sum = sum + cache[2][3] - cache[2][1].sum = 16 + 24 - 7 = 33
Calculate the peak number of users

4 of 5

Created with Fabric.js 3.6.6 Input Grid Cache Grid 1 4 7 2 5 8 3 6 9 0 0 0 1 4 7 3 9 15 6 15 24 After we have iterated over the rows of interest, the final sum comes out to be 33.
Calculate the peak number of users

5 of 5

Smart caching#

Similar to our approach from above, where we pre-calculated the prefix sum for a row, we can pre-compute a cumulative region sum with respect to the origin at (0,0)(0, 0).

For a cell that is represented by its coordinates (row,col)(row, col), we will compute the cumulative region sum from the origin at (0,0)(0, 0) and cache that using the following formula:

cache[row][col]=i=0i=rowj=0j=colusers[i][j]cache[row][col] = \sum_{i = 0}^{i = row}\sum_{j = 0}^{j = col}users[i][j]

We can use the formulation given above for pre-calculating the cumulative sum for all the regions. However, we can do this more efficiently by making use of the cumulative sum of the regions that has already been calculated:

cache[i+1][j+1]=cache[i+1][j]+cache[i][j+1]+users[i][j]cache[i][j]cache[i + 1][j + 1] = cache[i + 1][j] + cache[i][j + 1] + users[i][j] - cache[i][j]

Here ii and jj range from 00 to the number of rows and columnsnumber\ of\ rows\ and\ columns, respectively, and the output cache is of order rows+1×cols+1rows + 1 \times cols + 1

Note: For the sake of simplicity and making the calculations easier to understand, we will set all the elements in the zeroth row and the column of the cache to zero.

Let’s review an illustration that represents the cumulative sum of the region:

Created with Fabric.js 3.6.6 1 4 7 2 5 8 3 6 9 Input Grid Cache Grid We initialize the cache grid with zeros in each of its cells. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Pre-computing the cumulative sum of the region

1 of 11

Created with Fabric.js 3.6.6 Input Grid Cache Grid 1 4 7 2 5 8 3 6 9 We iterate over the cells of both the grids one by one,updating the value of the next cell in the cache grid. 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
Pre-computing the cumulative sum of the region

2 of 11

Created with Fabric.js 3.6.6 Input Grid Cache Grid We iterate over the cells of both the grids one by one,updating the value of the next cell in the cache grid. 1 4 7 2 5 8 3 6 9 0 0 0 0 0 1 0 0 0 3 0 0 0 0 0 0
Pre-computing the cumulative sum of the region

3 of 11

Created with Fabric.js 3.6.6 Input Grid Cache Grid We iterate over the cells of both the grids one by one,updating the value of the next cell in the cache grid. 0 0 0 0 0 1 0 0 0 3 0 0 0 6 0 0 1 4 7 2 5 8 3 6 9
Pre-computing the cumulative sum of the region

4 of 11

Created with Fabric.js 3.6.6 Input Grid Cache Grid We iterate over the cells of both the grids one by one,updating the value of the next cell in the cache grid. 1 4 7 2 5 8 3 6 9 0 0 0 0 0 1 5 0 0 3 0 0 0 6 0 0
Pre-computing the cumulative sum of the region

5 of 11

Created with Fabric.js 3.6.6 Input Grid Cache Grid We iterate over the cells of both the grids one by one,updating the value of the next cell in the cache grid. 1 4 7 2 5 8 3 6 9 0 0 0 0 0 1 5 0 0 3 12 0 0 6 0 0
Pre-computing the cumulative sum of the region

6 of 11

Created with Fabric.js 3.6.6 Input Grid Cache Grid We iterate over the cells of both the grids one by one,updating the value of the next cell in the cache grid. 1 4 7 2 5 8 3 6 9 0 0 0 0 0 1 5 0 0 3 12 0 0 6 21 0
Pre-computing the cumulative sum of the region

7 of 11

Created with Fabric.js 3.6.6 Input Grid Cache Grid We iterate over the cells of both the grids one by one,updating the value of the next cell in the cache grid. 1 4 7 2 5 8 3 6 9 0 0 0 0 0 1 5 12 0 3 12 0 0 6 21 0
Pre-computing the cumulative sum of the region

8 of 11

Created with Fabric.js 3.6.6 Input Grid Cache Grid We iterate over the cells of both the grids one by one,updating the value of the next cell in the cache grid. 1 4 7 2 5 8 3 6 9 0 0 0 0 0 1 5 12 0 3 12 27 0 6 21 0
Pre-computing the cumulative sum of the region

9 of 11

Created with Fabric.js 3.6.6 Input Grid Cache Grid We iterate over the cells of both the grids one by one,updating the value of the next cell in the cache grid. 0 0 0 0 0 1 5 12 0 3 12 27 0 6 21 45 1 4 7 2 5 8 3 6 9
Pre-computing the cumulative sum of the region

10 of 11

Created with Fabric.js 3.6.6 Input Grid Cache Grid Each cell in the cache grid contains the cumulative region sum with respect to the origin at (0, 0). 0 0 0 0 0 1 5 12 0 3 12 27 0 6 21 45 1 4 7 2 5 8 3 6 9
Pre-computing the cumulative sum of the region

11 of 11

The cumulative sum of the region is calculated with respect to the origin. Therefore, we have to ensure that the sub-regions that are not part of the queried region are subtracted. We can extract the sum for the region, which is identified by the coordinates (row1,col1)(row1, col1) and (row2,col2)(row2, col2), from the cache with the following formula:

sum[row1...row2][col1...col2]=cache[row2+1][col2+1]cache[row1][col2+1]cache[row2+1][col1]+cache[row1][col1]sum[row1...row2][col1...col2] = cache[row2 + 1][col2 + 1] - cache[row1][col2 + 1] - cache[row2 + 1][col1] + cache[row1][col1]

Note: We used the principle of inclusion-exclusion here.

We will add the cumulative sum of the region cache[row1][col1]cache[row1][col1], because this region is covered twice by both cache[row1][col2+1]cache[row1][col2 + 1] and cache[row2+1][col1]cache[row2 + 1][col1].

Let’s review an example of this:

Created with Fabric.js 3.6.6 Input Grid Cache Grid Given the starting and ending coordinates of the subset region (1, 1) and (2, 2), we will use the pre-computed cache grid to calculate the sum. 1 4 7 2 5 8 3 6 9 0 0 0 0 0 1 5 12 0 3 12 27 0 6 21 45
Calculate the peak number of users

1 of 5

Created with Fabric.js 3.6.6 Input Grid Cache Grid 1 4 7 2 5 8 3 6 9 The region sum for (row2 = 2, col2 = 2) with respect to the origin (0, 0) is 45. But, we need to make sure that the blue highlighted region is not part of the sum. 0 0 0 0 0 1 5 12 0 3 12 27 0 6 21 45
Calculate the peak number of users

2 of 5

Created with Fabric.js 3.6.6 Input Grid Cache Grid 1 4 7 2 5 8 3 6 9 We subtract the sum of the blue region from the actual sum: sum = sum - 6 = 45 - 6 = 39. 0 0 0 0 0 1 5 12 0 3 12 27 0 6 21 45
Calculate the peak number of users

3 of 5

Created with Fabric.js 3.6.6 Input Grid Cache Grid 1 4 7 2 5 8 3 6 9 0 0 0 0 0 1 5 12 0 3 12 27 0 6 21 45 We subtract the sum of the blue region from the actual sum: sum = sum - 12 = 39 - 12 = 27.
Calculate the peak number of users

4 of 5

Created with Fabric.js 3.6.6 Input Grid Cache Grid 0 0 0 0 0 1 5 12 0 3 12 27 0 6 21 45 1 4 7 2 5 8 3 6 9 Notice, that the cell (0, 0) was part of both the regions thatwe excluded from our sum twice. Thus we need to add it backto the sum: sum = sum + 1 = 27 + 1 = 28
Calculate the peak number of users

5 of 5

Peak number of users

Complexity measures#

Method Time complexity Space complexity
brute_force O(mn)O(m*n) O(1)O(1)
cache_rows O(m)O(m) O(mn)O(m * n)
cache_smart O(1)O(1) O(mn)O(m * n)

Here mm and nn will represent the number of rows and columns, respectively.

Time complexity#

Let’s look at the time complexities for the methods, one by one:

  • brute_force: O(m×n)O(m \times n) time per query.
  • cache_rows: O(m)O(m) time per query, O(m×n)O(m \times n) time pre-computation
    • The pre-computation in the constructor will take O(m×n)O(m \times n) time.
    • The cache_rows query will take O(m)O(m) time.
  • cache_smart: O(1)O(1) time per query, O(m×n)O(m \times n) time pre-computation
    • The pre-computation in the constructor will take O(m×n)O(m \times n) time.
    • Each cache_smart query will take O(1)O(1) time.

Space complexity#

Similarly, for the space complexity:

  • brute_force: Since the algorithm only uses a constant amount of additional space, the space complexity will be O(1)O(1).
  • cache_rows: The algorithm will use O(m×n)O(m \times n) space to store the cumulative sum of all the rows.
  • cache_smart: The algorithm will use O(m×n)O(m \times n) space to store the cumulative sum of the region.

Feature #3: Power Up the Station

Feature #5: Densest Deployment